package com.cuz.daileetcode.utils;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.Optional;

/**
 * @author cuzz
 * @version 1.0
 * @description: 前缀树
 * @date 22:43 2021/12/13
 **/
public class PrefixTree<T> {
    /**
     * 根节点
     * <p>
     * 其 curNodeNext 表示从根节点开始存在多少条路（如果包含节点的话那么就有）
     */
    private PrefixTreeNode<T> rootNode;

    /***
     * 节点
     * @param <T>
     */
    public static class PrefixTreeNode<T> {
        //节点也可以不存储值
        private T value;
        //这个节点比经过多少次了
        public int pass;
        //这个节点被作为结尾节点几次
        public int end;
        //接下来的路 T33 表示路上的内容 PrefixTreeNode<T33>表示路下一个节点
        public Map<T, PrefixTreeNode<T>> curNodeNext;

        private PrefixTreeNode() {

        }

        /**
         * 新建一个节点
         *
         * @param value 节点值
         * @return 初始化节点
         */
        public static <T> PrefixTreeNode<T> create(T value) {
            PrefixTreeNode<T> node = new PrefixTreeNode<>();
            node.pass = 0;
            node.end = 0;
            node.curNodeNext = new HashMap<>();
            node.value = value;
            return node;
        }

    }

    private PrefixTree() {

    }

    /****
     * 新建一个前缀树
     * @param <T>
     * @return 初始化前缀树
     */
    public static <T> PrefixTree<T> create() {
        PrefixTree<T> tree = new PrefixTree<>();
        tree.rootNode = PrefixTreeNode.create(null);
        return tree;
    }

    public void insert(T... t) {
        //根节点的end++
        rootNode.pass++;
        //当前节点是根节点
        PrefixTreeNode<T> curNode = this.rootNode;
        //比如 a b c
        for (T temp : Objects.requireNonNull(t)) {
            //从当前节点中 拿 a
            PrefixTreeNode<T> nextRoadNode = curNode.curNodeNext.get(temp);
            //不存在a
            if (nextRoadNode == null) {
                //新建a
                nextRoadNode = PrefixTreeNode.create(temp);
            }
            //pass++
            nextRoadNode.pass++;
            //重写put 回去
            curNode.curNodeNext.put(temp, nextRoadNode);
            //更新下一个节点为a 下一次循环 temp=b
            curNode = nextRoadNode;
        }
        //最后curNode是结束的节点 如c 让c的end++ 表示以c结尾次数加1
        curNode.end++;
    }

    /***
     * 查找序列
     * @param prefix
     * @return
     */
    public Optional<PrefixTreeNode<T>> findSequence(T... prefix) {
        PrefixTreeNode<T> curNode = this.rootNode;
        for (T temp : Objects.requireNonNull(prefix)) {
            PrefixTreeNode<T> nodeInRoad = curNode.curNodeNext.get(temp);
            //当前节点后续释放存在此节点 如果不存在说明不存在以这个序列为前缀的
            //比如 前缀树存在 abc 如果查找ad 那么 第一次循环temp=a 存在 刷新curNode 为a
            //第二次循环temp=d 不存在了 返回empty
            if (nodeInRoad == null) {
                return Optional.empty();
            }
            //更新当前node
            curNode = nodeInRoad;
        }
        //如果是 abc 查找 abd 最后curNode为 c 返回node
        return Optional.of(curNode);
    }

    /***
     * 这个序列出现过几次
     * @param seq
     * @return
     */
    public int countSequenceEqual(T... seq) {
        return findSequence(seq).map(node -> node.end).orElse(0);
    }

    /**
     * 这个序列作为前缀出现过几次
     * @param seq
     * @return
     */
    public int countSequenceAsPrefix(T... seq) {
        return findSequence(seq).map(node -> node.pass).orElse(0);
    }

    /**
     * 删除序列
     *
     * @param seq
     */
    public void delete(T... seq) {
        //边界处理 不存在此序列直接返回
        if (seq == null || seq.length == 0 || countSequenceEqual(seq) < 0) {
            return;
        }
        //当前节点
        PrefixTreeNode<T> curNode = this.rootNode;
        rootNode.pass--;
        for (T temp : seq) {
            //如果减小到0了说明这个路已经无法到达了 删除这个节点表示无法到达
            PrefixTreeNode<T> nextNode = curNode.curNodeNext.get(temp);
            if (--nextNode.pass == 0) {
                curNode.curNodeNext.remove(temp);
                return;
            }
            //刷新curNode
            curNode = nextNode;
        }
        //走到这一步说明 路没断 那么end--
        curNode.end--;
    }
}
